//
//  main.c
//  Test
//
//  Created by wangrui on 14-9-22.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

/*
 *稀疏矩阵，使用邻接表替代邻接矩阵存储图的信息 2014-09-24 11:09:33
 *适合于 边数m远小于点数n的平方
 */

/* 	测试数据
 *  4 5
 	1 4 9
 	2 4 6
 	1 2 5
 	4 3 8
 	1 3 7
 */


#include <stdio.h>

void printArray(int a[], int count)
{
	for (int k=0; k<count; k++) {
		printf("%d ",a[k]);
	}
	
	printf("\n");
}

int main(int argc, const char * argv[]) {
	
	int n,m; //顶点数，边数
	scanf("%d %d",&n,&m);
	
	int u[m+1],v[m+1],w[m+1];  //存储有边的顶点信息
	int first[n+1], next[n+1]; //first数组用于存入分配的边, next 数组用于存放相同顶点的下一条边
	
	//初始化
	for (int i=0; i<=n; i++) {
		first[i] = -1;
		next[i] = -1;
	}
	
	//存入边
	for (int i=1; i<=m; i++) {
		scanf("%d %d %d",&u[i],&v[i],&w[i]);//存入某个顶点值到第i边对应的顶点数组
		next[i] = first[u[i]];
		first[u[i]] = i;
	}
	
	printf("\n");
	//遍历每个顶点的边
	for (int i=1; i<=n; i++) {
		
		int k = first[i];
		if (k==-1) {
			printf("第%d点:没有对应边 \n",i);
			continue;
		}
		
		printf("第%d点:",i);
		while (k!=-1) {
			printf("%d",k);
			printf("(%d->%d weight:%d) ",u[k],v[k],w[k]);
			k = next[k];
		}
		printf("\n");
	}
	
	
	
    return 0;
}
